package problemLCR130;

//LCR 130.衣橱整理
//https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

class Solution {
    int n,m,ret;
    int[] xx = {1,-1,0,0};
    int[] yy = {0,0,1,-1};
    boolean[][] st;
    public int wardrobeFinishing(int _m, int _n, int cnt) {
        n = _n;
        m = _m;
        st = new boolean[m][n];
        dfs(0,0,cnt);
        return ret;
    }
    public void dfs(int x, int y, int cnt) {
        st[x][y] = true;
        ret++;
        //向右
        if(y+1 < n && digit(x) + digit(y + 1) <= cnt && !st[x][y+1]) dfs(x, y+1, cnt);
        //向下
        if(x+1 < m && digit(x+1) + digit(y) <= cnt && !st[x+1][y]) dfs(x+1, y, cnt);
    }

     public int digit(int x) {
        int sum = 0;
        while (x != 0) {
            sum += x%10;
            x /= 10;
        }
        return sum;
    }
}